/*
 * LinkedList.h
 *
 *  Created on: 2013年7月30日
 *      Author: sun
 */

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include <unistd.h>
#include <errno.h>

#define offsetof(type, member) (size_t)&(((type *)0)->member)

namespace sdfs {
template <typename T>
class LinkedList {
	typedef struct _LinkedNode{
		T	data;
		struct _LinkedNode *pre;
		struct _LinkedNode *next;
	}LinkedNode;
public:
	LinkedList()
	{
		m_nCount = 0;
		m_pNodes = NULL;
	}
	virtual ~LinkedList()
	{
		T ptr = Pop();
		while(ptr != NULL)
		{
			Pop();
		}
		m_pNodes = NULL;
	}

	T GetAt(unsigned int pos)
	{
		if(pos < 0 || pos > m_nCount)
			return NULL;
		if(m_nCount == 0)
		{
			return NULL;
		}
		LinkedNode *ptr = m_pNodes;
		if(pos > m_nCount/2)
		{
			//pre
			int count = m_nCount - pos + 1;
			while(count--)
			{
				ptr = ptr->pre;
			}
		}
		else
		{
			//next
			int count = pos;
			while(count--)
			{
				ptr = ptr->next;
			}
		}
		return ptr->data;
	}

	int Insert(T data, unsigned int pos)
	{
		if(pos < 0 || pos > m_nCount)
			return -1;
		if(m_nCount == 0)
		{
			m_pNodes = new LinkedNode;
			m_pNodes->data = data;
			m_pNodes->pre = m_pNodes;
			m_pNodes->next = m_pNodes;
			m_nCount++;
			return 0;
		}

		LinkedNode *ptr = m_pNodes;
		if(pos > m_nCount/2)
		{
			//pre
			int count = m_nCount - pos;
			while(count--)
			{
				ptr = ptr->pre;
			}
		}
		else
		{
			//next
			int count = pos;
			while(count--)
			{
				ptr = ptr->next;
			}
		}
		LinkedNode *pnode = new LinkedNode;
		pnode->data = data;
		pnode->pre = ptr->pre;
		pnode->next = ptr;
		ptr->pre->next = pnode;
		ptr->pre = pnode;
		m_nCount++;
		return 0;
	}

	int Push(T data)
	{
		return Insert(data, m_nCount);
	}

	T GetLast()
	{
		if( 0 == m_nCount)
			return NULL;
		return m_pNodes->pre->data;
	}

	T Pop()
	{
		T data = GetLast();
		if(data != NULL)
		{
			LinkedNode *ptr = m_pNodes->pre;
			m_pNodes->pre->pre->next = m_pNodes;
			m_pNodes->pre = m_pNodes->pre->pre;
			delete ptr;
			ptr = NULL;
			m_nCount--;
		}
		return data;
	}

	int Size()
	{
		return m_nCount;
	}

private:
	unsigned int		m_nCount;
	LinkedNode	*m_pNodes;
};

} /* namespace sdfs */
#endif /* LINKEDLIST_H_ */
